

#include "stdafx.h"

#include "Utils.h"


#define M 5

int aMap[M][M] = { {7,0,0,0,0},
				   {3,8,0,0,0},
				   {8,1,0,0,0},
				   {2,7,4,4,0},
				   {4,5,2,6,5} };
int aMaxSum[M][M] = { 0 };

#ifdef TEST_BED
int main()
#else
int main_()
#endif
{
	//Step1. Init aMaxSum[M]
	int sum = 0;
	for (int i = 0; i < M; i++) {
		sum += aMap[i][0];
		aMaxSum[i][0] = sum;
	}

	//Step2. Backstepping down
	//Recursion Formula is aMaxSum[i][j] = MAX(aMaxSum[i-1][j-1], aMaxSum[i-1][j]) + aMap[i][j];
	for (int i = 1; i < M; i++) {
		for (int j = 1; j <= i; j++) {
			aMaxSum[i][j] = MAX(aMaxSum[i - 1][j - 1], aMaxSum[i - 1][j]) + aMap[i][j];
		}
	}

	for (int i = 0; i < M; i++)
		printf("maxSum = %d\n", aMaxSum[M-1][i]);

    return 0;
}


#if 0
//Step1. Init aMaxSum[M]
for (int i = 0; i < M; i++)
	aMaxSum[M - 1][i] = aMap[M - 1][i];

//Step2. Backstepping up
//Recursion Formula is aMaxSum[i][j] = MAX(aMaxSum[i+1][j], aMaxSum[i+1][j+1]) + aMap[i][j];
for (int i = M - 1; i > 0; i--) {
	for (int j = 0; j < i; j++) {
		aMaxSum[i - 1][j] = MAX(aMaxSum[i][j], aMaxSum[i][j + 1]) + aMap[i - 1][j];
	}
}
#endif
